Programs consist of blocks or strings of sequential instructions, which have a single entry point (the first instruction) and a single exit point (the last instruction). There can be a choice from a number of instruction blocks to be executed after any particular block. When there is more than one possible block, one or more conditions must be used to determine which block to choose. The pattern of links between blocks is called the program's control or flow graph.
These blocks of instructions are packed together in memory. When there is no choice of subsequent block (block B), it can normally be placed immediately after the first block (block A). This means that there need not be any explicit change in control to get from block A to block B. Some blocks have a choice of successor blocks. Clearly only one of the successors, for example block B, can be placed sequentially afterwards. The other block, block C, is indicated explicitly within block A. A conditional mechanism is used to determine which block is to be chosen. If the condition is met, then the chosen successor block is block C. If the condition is not met, then the chosen successor is block B. These are conditional branches.
Branches are well known in the art and are essential for a computer system to execute any program. Known computer systems typically contain a special register, the program counter register, which provides an indication of the address of the next instruction to execute. This register is usually automatically incremented after an instruction executes, so that it now indicates the address of the next sequential instruction. Branch instructions are used to change this behavior. These branch instructions specify an alternative address (the target location) for the next executable instruction. Conditional branch instructions also specify a condition which must be met for the alternative address to be used, otherwise the program counter is incremented as usual. These branch instructions thus define the end of a block of instructions.
A typical program must perform branching operations in numerous places, called branch points, as it executes. Each branch point has a particular branching function associated with it, which usually differs from the branching functions at most other branch points. A branching function can be defined in terms of a vector of M conditional expressions and a set of at most 2M possible target addresses. A processor evaluates these conditional expressions whenever program execution reaches a branch point to which the branching function applies, and thus generates a vector of M boolean values. The branching function maps each of the 2M possible values of this vector to some target address in the program's instruction memory. Programmers wish to write code which executes as few instructions as possible to evaluate the branching function and then perform the branch at each branch point. The twin goals are to minimize the size of the executable code and to maximize execution performance, while maintaining flexibility.
Most general-purpose microprocessors provide a variety of simple two-way conditional branch instructions, in which a branch is taken or not taken depending on whether one particular conditional expression is true or false. If a branch point requires evaluation of more than one conditional expression, and can cause execution to jump to one of more than two possible targets, then a program must execute multiple simple two-way conditional branch instructions. Complex branching patterns, in which a program must evaluate multiple conditional expressions and jump to one of several possible targets from one particular location in the code, occur naturally in a wide variety of computational situations. Programmers typically wish to write code which requires as few instructions as possible and which executes as quickly as possible when performing such complex branch decisions.